package NO1_Array;

/**
 * 2025-6-23
 * 力扣 - 169.多数元素
 * <p>
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。
 * 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 */
public class MajorityElementMain {
    public static void main(String[] args) {

        int[] nums = {3, 3, 3, 3, 2};

        System.out.println(majorityElement(nums));
    }

    // 排序之后取中间的值，有点小聪明的感觉
//    public static int majorityElement(int[] nums) {
//        Arrays.sort(nums);
//        return nums[nums.length / 2];
//    }

    // Map 方法
//    public static int majorityElement(int[] nums) {
//        // num , 出现的次数
//        HashMap<Integer, Integer> countMap = new HashMap<>();
//        int len = nums.length;
//        for (int num : nums) {
//            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
//            if (countMap.get(num) > len / 2) {
//                return num;
//            }
//        }
//        return -1;
//    }

    // 摩尔投票法
    // 没搞懂
    // 假设数组中每个不同的数字就代表一个国家，而数字的个数就代表这个国家的人数，他们在一起混战，就是每两个两个同归于尽。我们就可以知道那个人数大于数组长度一半的肯定会获胜。
    public static int majorityElement(int[] num) {
        int major = num[0];
        int count = 1;
        for (int i = 1; i < num.length; i++) {
            int count1 = num[i];
            if (count == 0) {
                //前面都消完了，在重新赋值
                count++;
                major = num[i];
            } else if (major == num[i]) {
                //自己人，count就加1
                count++;
            } else {
                //不是自己人就同归于尽，消掉一个
                count--;
            }
        }
        return major;
    }
}
